package com.company.algo.listnode;

import com.company.algo.pojo.ListNode;

/**
 * https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484467&idx=1&sn=beb3ae89993b812eeaa6bbdeda63c494&scene=21#wechat_redirect
 * 递归的思想相对迭代思想，稍微有点难以理解，处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。
 * 处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题。
 */
public class ReverseNodes {
    /** 递归的使用一定要紧扣定义，不要跳进递归（你的脑袋能压几个栈呀？）
     * @param head 输入一个节点head
     * @return 将「以head为起点」的链表反转，并返回反转之后的头结点
     */
    ListNode reverse(ListNode head){
        if (head.next == null) return head;
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    // 将链表的前 n 个节点反转（n <= 链表长度）
    ListNode successor = null; // 后驱节点
    ListNode reverseN(ListNode head, int n){
        if (n==1) {
            //记录第n+1个节点
            successor = head.next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next,n-1);
        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }

    //反转区间[m,n]（索引从 1 开始）中的链表元素,返回反转后的头结点
    ListNode reverseBetween(ListNode head, int m, int n){
        //base case
        if (m==1){
            //相当于反转前n个元素
            return reverseN(head,n);
        }
        // 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next,m-1,n-1);
        return head;
    }

}
